#include <iostream>
#include <string>
using namespace std;

const int max_count = 128;

template< typename T >
int LCS( T* seq1, T* seq2, int len1, int len2 )
{
	int F[ max_count ] = {0};
	for( int i = 1; i <= len2; i++ )
	{
		int t = F[0];
		for( int j = 1; j <= len1; j++ )
		{
			int q = F[j];
			if( seq1[j - 1] == seq2[i - 1] )
			{
				F[j] = t + 1;
			}
			else
			{
				if( F[j] < F[j - 1] ) F[j] = F[j - 1];
			}
			t = q;
		}
	}
	return F[len1];
}

int main( int argc, char* argv[] )
{
	int c = 1;
	while( 1 )
	{
		char seq1[ max_count ] = {0};
		char seq2[ max_count ] = {0};

		cin.getline( seq1, max_count - 1 );
		if( seq1[0] == '#' ) break;
		cin.getline( seq2, max_count - 1 );

		cout << "Case #" << c++ << ": you can visit at most " << LCS( seq1, seq2, strlen(seq1), strlen(seq2) ) << " cities." << endl;
	}
	return 0;
}
